import java.util.Arrays;

/**
* @description: 825. 适龄的朋友
* @author hewei
* @date 2022/9/1 15:02
* @version 1.0
*/

public class NumFriendRequests {

    public static void main(String[] args) {
        int[] nums = {73,106,39,6,26,15,30,100,71,35,46,112,6,60,110};
        System.out.println(new NumFriendRequests().numFriendRequests(nums));
    }

    public int numFriendRequests1(int[] ages) {
        Arrays.sort(ages);
        int ans = 0;
        int count = 1;
        for (int i = 1; i < ages.length; i++) {
            if (ages[i] == ages[i - 1]) ++count;
            if (i != ages.length - 1 && ages[i + 1] == ages[i]) continue;
            int l = 0;
            int r = i - 1;
            double target = ages[i] * 0.5 + 7;
            if (ages[r] <= target) {
                count = 1;
                continue;
            }
            while (l < r) {
                int mid = (r - l) / 2 + l;
                if (ages[mid] <= target) {
                    l = mid + 1;
                } else r = mid;
            }
            ans += (i - l) * count;
            count = 1;
        }
        return ans;
    }

    public int numFriendRequests2(int[] ages) {
        Arrays.sort(ages);
        int ans = 0, left = 0, right = 0;
        for (int age : ages) {
            if (age < 15) continue;
            while (ages[left] <= age * 0.5 + 7) ++left;
            while (right < ages.length - 1 && ages[right + 1] <= age) ++right;
            ans += right - left;
        }
        return ans;
    }

    public int numFriendRequests(int[] ages) {
        int[] temp = new int[121];
        for (int age : ages) {
            temp[age]++;
        }
        int[] pre = new int[121];
        for (int i = 1; i < 121; i++) {
            pre[i] = pre[i - 1] + temp[i];
        }
        int ans = 0;
        for (int i = 15; i < 121; i++) {
            if (temp[i] != 0) {
                ans += temp[i] * (pre[i] - pre[i / 2 + 7] - 1);
            }
        }
        return ans;
    }
}
